package learn.linkedListImpl;


public class ReverseLinkedList {


    /**
     * 链表反转
     * @param head
     * @return
     *
     * 使用双指针法
     *
     */
    public ListNode reverseList(ListNode head){

        //设置两个指针
        ListNode perv = null;
        ListNode cur = head;
        ListNode temp = null;

        //循环处理数据
        while (cur!=null){
            // 保存下一个节点
            temp = cur.next;
            //当前节点next指向前期
            cur.next = perv;
            //将当前节点设置为前驱
            perv = cur;
            //将下一个节点设置为当前节点
            cur = temp;
        }
        return perv;
    }

    public ListNode reverseList01(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        // 先保存下一个节点
        temp = cur.next;
        // 反转
        cur.next = prev;
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }



}
